package com.Offer;

/*
    面试题14：剪绳子
    题目:给一根长度为n的绳子，请把绳子剪成m段(m、n都是整数，并且n>1，m>1),每段绳子的长度记为k[0],k[1],k[2]...k[m]。
    请问这些绳子的长度的最大成绩是多少。例如当绳子长度为8时，我们把它剪成长度分别为3,3,2的三段，此时最大乘积为18
 */
public class demo14 {
    public static void main(String[] args) {
        System.out.println(maxProductAfterCutting_solution(8));
    }

    public static int maxProductAfterCutting_solution(int length){
        if(length < 2)
            return 0;
        if(length == 2)
            return 1;
        if(length == 3)
            return 2;

        int[] products = new int[length+1];
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;

        int max = 0;

        for(int i = 4;i<=length;i++){
            max = 0;
            for(int j = 1;j<=i/2;j++){
                int product = products[j]*products[i-j];
                if(max < product){
                    max = product;
                }
                products[i] = max;
            }
        }
        max = products[length];
        return max;
    }
}
